//69. x 的平方根

//给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
//由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
//注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x * *0.5 。

//class Solution {
//    const int SQRT_INT_MAX = sqrt(INT_MAX);
//public:
//    int mySqrt(int x) {
//        int left = 0, right = min(x, SQRT_INT_MAX) + 1, mid{};
//        while (left + 1 < right) {
//            mid = left + (right - left) / 2;
//            (mid * mid <= x ? left : right) = mid;
//        }
//        return left;
//    }
//};

//74. 搜索二维矩阵

//给你一个满足下述两条属性的 m x n 整数矩阵：
//每行中的整数从左到右按非严格递增顺序排列。
//每行的第一个整数大于前一行的最后一个整数。
//给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

//class Solution {
//public:
//    bool searchMatrix(vector<vector<int>>& matrix, int target) {
//        int m = matrix.size(), n = matrix[0].size();
//        int left = -1, right = m * n, mid{}, x{};
//        while (left + 1 < right) {
//            mid = left + (right - left) / 2;
//            x = matrix[mid / n][mid % n];
//            if (x == target) {
//                return true;
//            }
//            (x < target ? left : right) = mid;
//        }
//        return false;
//    }
//};

//2476. 二叉搜索树最近节点查询

//给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
//请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
//mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 - 1 代替。
//maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 - 1 代替。
//返回数组 answer 。

///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//    vector<int> a;
//
//    void dfs(TreeNode* node) {
//        if (node == nullptr) {
//            return;
//        }
//        dfs(node->left);
//        a.push_back(node->val);
//        dfs(node->right);
//    };
//
//public:
//    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
//        dfs(root);
//        int n = a.size(), j{}, mx{}, mn{};
//        vector<vector<int>> ans;
//        for (int q : queries) {
//            j = ranges::lower_bound(a, q) - a.begin();
//            mx = j < n ? a[j] : -1;
//            if (j == n || a[j] != q) { // a[j]>q, a[j-1]<q
//                j--;
//            }
//            mn = j >= 0 ? a[j] : -1;
//            ans.emplace_back({ mn, mx });
//        }
//        return ans;
//    }
//};

//278. 第一个错误的版本

//你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
//假设你有 n 个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
//你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

//class Solution {
//public:
//    int firstBadVersion(int n) {
//        int left = 0, right = n, mid{};
//        while (left + 1 < right) {
//            mid = left + (right - left) / 2;
//            (isBadVersion(mid) ? right : left) = mid;
//        }
//        return right;
//    }
//};

//374. 猜数字大小

//我们正在玩猜数字游戏。猜数字游戏的规则如下：
//我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
//如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。
//你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有三种可能的情况：
//- 1：你猜的数字比我选出的数字大 （即 num > pick）。
//1：你猜的数字比我选出的数字小 （即 num < pick）。
//0：你猜的数字与我选出的数字相等。（即 num == pick）。
//返回我选出的数字。

///**
// * Forward declaration of guess API.
// * @param  num   your guess
// * @return 	     -1 if num is higher than the picked number
// *			      1 if num is lower than the picked number
// *               otherwise return 0
// * int guess(int num);
// */
//
//class Solution {
//public:
//    int guessNumber(int n) {
//        int l = 0, r = n, mid{};
//        while (l + 1 < r) {
//            mid = l + (r - l) / 2;
//            if (!guess(mid)) {
//                return mid;
//            }
//            (guess(mid) <= 0 ? r : l) = mid;
//        }
//        return r;
//    }
//};

//162. 寻找峰值

//峰值元素是指其值严格大于左右相邻值的元素。
//给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
//你可以假设 nums[-1] = nums[n] = -∞ 。
//你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

//class Solution {
//public:
//    int findPeakElement(vector<int>& nums) {
//        int l = -1, r = nums.size() - 1, mid{};
//        while (l + 1 < r) {
//            mid = l + (r - l) / 2;
//            (nums[mid] > nums[mid + 1] ? r : l) = mid;
//        }
//        return r;
//    }
//};

//1901. 寻找峰值 II

//一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
//给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置[i, j] 。
//你可以假设整个矩阵周边环绕着一圈值为 - 1 的格子。
//要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法

//class Solution {
//public:
//    vector<int> findPeakGrid(vector<vector<int>>& mat) {
//        auto get_maxi = [&](vector<int> arr) -> int {
//            return ranges::max_element(arr) - arr.begin();
//            };
//
//        int l = -1, r = mat.size() - 1, y{}, x{};
//        while (l + 1 < r) {
//            y = l + (r - l) / 2;
//            x = get_maxi(mat[y]);
//            (mat[y][x] > mat[y + 1][x] ? r : l) = y;
//        }
//        return { r, get_maxi(mat[r]) };
//    }
//};

//852. 山脉数组的峰顶索引

//给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
//返回峰值元素的下标。
//你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int l = 0, r = arr.size() - 2, mid{};
//        while (l + 1 < r) {
//            mid = l + (r - l) / 2;
//            (arr[mid] > arr[mid + 1] ? r : l) = mid;
//        }
//        return r;
//    }
//};

//1095. 山脉数组中查找目标值

//（这是一个 交互式问题 ）
//你可以将一个数组 arr 称为 山脉数组 当且仅当：
//arr.length >= 3
//存在一些 0 < i < arr.length - 1 的 i 使得：
//arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
//arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
//给定一个山脉数组 mountainArr ，返回 最小 的 index 使得 mountainArr.get(index) == target。如果不存在这样的 index，返回 - 1 。
//你无法直接访问山脉数组。你只能使用 MountainArray 接口来访问数组：
//MountainArray.get(k) 返回数组中下标为 k 的元素（从 0 开始）。
//MountainArray.length() 返回数组的长度。
//调用 MountainArray.get 超过 100 次的提交会被判定为错误答案。此外，任何试图绕过在线评测的解决方案都将导致取消资格。

///**
// * // This is the MountainArray's API interface.
// * // You should not implement it, or speculate about its implementation
// * class MountainArray {
// *   public:
// *     int get(int index);
// *     int length();
// * };
// */
//
//class Solution {
//    int binary_search(MountainArray& mountain, int target, int l, int r, int key(int)) {
//        target = key(target);
//        while (l <= r) {
//            int mid = l + (r - l) / 2;
//            int cur = key(mountain.get(mid));
//            if (cur == target) {
//                return mid;
//            }
//            else if (cur < target) {
//                l = mid + 1;
//            }
//            else {
//                r = mid - 1;
//            }
//        }
//        return -1;
//    }
//public:
//    int findInMountainArray(int target, MountainArray& mountainArr) {
//        int l = 0, r = mountainArr.length() - 1, mid{};
//        while (l < r) {
//            mid = l + (r - l) / 2;
//            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
//                l = mid + 1;
//            }
//            else {
//                r = mid;
//            }
//        }
//
//        int peak = l;
//        int index = binary_search(mountainArr, target, 0, peak, [](int x) -> int {return x; });
//        if (index != -1) {
//            return index;
//        }
//        return binary_search(mountainArr, target, peak + 1, mountainArr.length() - 1, [](int x) -> int {return -x; });
//    }
//};

//153. 寻找旋转排序数组中的最小值

//已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0, 1, 2, 4, 5, 6, 7] 在变化后可能得到：
//若旋转 4 次，则可以得到[4, 5, 6, 7, 0, 1, 2]
//若旋转 7 次，则可以得到[0, 1, 2, 4, 5, 6, 7]
//注意，数组[a[0], a[1], a[2], ..., a[n - 1]] 旋转一次 的结果为数组[a[n - 1], a[0], a[1], a[2], ..., a[n - 2]] 。
//给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
//你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int l = -1, r = nums.size() - 1, mid{};
//        while (l + 1 < r) {
//            mid = l + (r - l) / 2;
//            (nums[mid] < nums.back() ? r : l) = mid;
//        }
//        return nums[r];
//    }
//};

//154. 寻找旋转排序数组中的最小值 II

//已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0, 1, 4, 4, 5, 6, 7] 在变化后可能得到：
//若旋转 4 次，则可以得到[4, 5, 6, 7, 0, 1, 4]
//若旋转 7 次，则可以得到[0, 1, 4, 4, 5, 6, 7]
//注意，数组[a[0], a[1], a[2], ..., a[n - 1]] 旋转一次 的结果为数组[a[n - 1], a[0], a[1], a[2], ..., a[n - 2]] 。
//给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
//你必须尽可能减少整个过程的操作步骤。

//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int l = -1, r = nums.size() - 1, mid{};
//        while (l + 1 < r) {
//            mid = l + (r - l) / 2;
//            if (nums[mid] == nums[r]) {
//                r--;
//            }
//            else if (nums[mid] < nums[r]) {
//                r = mid;
//            }
//            else {
//                l = mid;
//            }
//        }
//        return nums[r];
//    }
//};

//33. 搜索旋转排序数组

//整数数组 nums 按升序排列，数组中的值 互不相同 。
//在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为[nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]（下标 从 0 开始 计数）。
//例如，[0, 1, 2, 4, 5, 6, 7] 下标 3 上向左旋转后可能变为[4, 5, 6, 7, 0, 1, 2] 。
//给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 - 1 。
//你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int last = nums.back();
//        int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
//        while (left + 1 < right) { // 开区间不为空
//            int mid = left + (right - left) / 2;
//            int x = nums[mid];
//            if (target > last && x <= last) { // target 在第一段，x 在第二段
//                right = mid; // 下轮循环去左边找
//            }
//            else if (x > last && target <= last) { // x 在第一段，target 在第二段
//                left = mid; // 下轮循环去右边找
//            }
//            else if (x >= target) { // 否则，x 和 target 在同一段
//                right = mid;
//            }
//            else {
//                left = mid;
//            }
//        }
//        return nums[right] == target ? right : -1;
//    }
//};

//81. 搜索旋转排序数组 II

//已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
//在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为[nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]
//（下标 从 0 开始 计数）。例如，[0, 1, 2, 4, 4, 4, 5, 6, 6, 7] 在下标 5 处经旋转后可能变为[4, 5, 6, 6, 7, 0, 1, 2, 4, 4] 。
//给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
//你必须尽可能减少整个操作步骤。

//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int left = -1, right = nums.size() - 1, mid{};
//        auto check = [&](int i) -> bool {
//            int x = nums[i];
//            if (x > nums[right]) {
//                return target > nums[right] && x >= target;
//            }
//            return target > nums[right] || x >= target;
//            };
//
//        while (left + 1 < right) {
//            mid = left + (right - left) / 2;
//            if (nums[mid] == nums[right]) {
//                right--;
//            }
//            else if (check(mid)) {
//                right = mid;
//            }
//            else {
//                left = mid;
//            }
//        }
//        return nums[right] == target;
//    }
//};

//222. 完全二叉树的节点个数

//给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
//完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
//若最底层为第 h 层（从第 0 层开始），则该层包含 1~2h 个节点。

///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    int countNodes(TreeNode* root) {
//        if (root == nullptr) {
//            return 0;
//        }
//        int level = 0;
//        TreeNode* node = root;
//        while (node->left != nullptr) {
//            level++;
//            node = node->left;
//        }
//        int low = 1 << level, high = (1 << (level + 1)) - 1;
//        while (low < high) {
//            int mid = (high - low + 1) / 2 + low;
//            if (exists(root, level, mid)) {
//                low = mid;
//            }
//            else {
//                high = mid - 1;
//            }
//        }
//        return low;
//    }
//
//    bool exists(TreeNode* root, int level, int k) {
//        int bits = 1 << (level - 1);
//        TreeNode* node = root;
//        while (node != nullptr && bits > 0) {
//            if (!(bits & k)) {
//                node = node->left;
//            }
//            else {
//                node = node->right;
//            }
//            bits >>= 1;
//        }
//        return node != nullptr;
//    }
//};

//1539. 第 k 个缺失的正整数

//给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
//请你找到这个数组里第 k 个缺失的正整数。

//class Solution {
//public:
//    int findKthPositive(vector<int>& arr, int k) {
//        if (arr[0] > k) {
//            return k;
//        }
//
//        int l = -1, r = arr.size(), mid{}, x{};
//        while (l + 1 < r) {
//            mid = (l + r) >> 1;
//            x = mid < arr.size() ? arr[mid] : INT_MAX;
//            (x - mid - 1 >= k ? r : l) = mid;
//        }
//
//        return k - (arr[r - 1] - (r - 1) - 1) + arr[r - 1];
//    }
//};

//540. 有序数组中的单一元素

//给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
//请你找出并返回只出现一次的那个数。
//你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

//class Solution {
//public:
//    int singleNonDuplicate(vector<int>& nums) {
//        int l = -1, r = nums.size() / 2, mid{};
//        while (l + 1 < r) {
//            mid = l + (r - l) / 2;
//            (nums[mid * 2] != nums[mid * 2 + 1] ? r : l) = mid;
//        }
//        return nums[r * 2];
//    }
//};

//4. 寻找两个正序数组的中位数

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//算法的时间复杂度应该为 O(log(m + n)) 。

//class Solution {
//public:
//    double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
//        if (a.size() > b.size()) {
//            swap(a, b); // 保证下面的 i 可以从 0 开始枚举
//        }
//
//        int m = a.size(), n = b.size();
//        a.insert(a.begin(), INT_MIN);
//        b.insert(b.begin(), INT_MIN);
//        a.push_back(INT_MAX);
//        b.push_back(INT_MAX);
//
//        // 循环不变量：a[left] <= b[j+1]
//        // 循环不变量：a[right] > b[j+1]
//        int left = 0, right = m + 1;
//        while (left + 1 < right) {
//            int i = (left + right) / 2;
//            int j = (m + n + 1) / 2 - i;
//            (a[i] <= b[j + 1] ? left : right) = i;
//        }
//
//        // 此时 left 等于 right-1
//        // a[left] <= b[j+1] 且 a[right] > b[j'+1] = b[j]，所以答案是 i=left
//        int i = left;
//        int j = (m + n + 1) / 2 - i;
//        int max1 = max(a[i], b[j]);
//        int min2 = min(a[i + 1], b[j + 1]);
//        return (m + n) % 2 ? max1 : (max1 + min2) / 2.0;
//    }
//};